704. 二分查找

#leetcode/binary-search

704. 二分查找

Similar Question

Solution Tips

方案一: 二分查找

  var searchInsert = function(nums, target) {
    let left = 0
    let right = nums.length-1
    let mid = 0
    let out = 0
    while(left<=right){ // 注意是等于
        mid = Math.floor((left+right)/2)
        if(nums[mid]==target) return mid
        if(nums[mid]<target){
            left = mid+1
        }else{
            right = mid-1
        }
    }
    return -1
  };

循环结束都没有找到，返回 -1

图展示了二分搜索算法的执行过程：

优化

const mid = left + Math.floor((right - left) / 2);

当 left 和 right 是很大的整数的时候，如果写 int mid = (left + right) / 2; 这里 left + right 的值就有可能超过 int 类型能表示的最大值，因此使用 mid = left + (right - left) // 2 可以避免这种情况。

事实上，mid = left + (right - left) // 2 在 right 很大、 left 是负数且很小的时候， right - left 也有可能超过 int 类型能表示的最大值，只不过一般情况下 left 和 right 表示的是数组索引值，left 是非负数，因此 right - left 溢出的可能性很小。

在这里补充一个小细节：除以 2 这件事情，还可以用右移 1 位来代替，位移运算的效率更高些。具体来说是这样：

mid = left + (right - left) // 2

mid = (left + right) >> 1

int mid = l + (r - l) / 2;            

int mid = (left + right) >>> 1;

注意：Java 中要使用 >>> 表示无符号右移，有符号位移是不行的。

你没有看错，请注意，我现在又告诉你取 (left + right) 的一半，但不是除以 2 ，而是无符号右移一位，理由如下：

  1. left 和 right 一般表示数组或列表的索引，它们都是正数；
  2. 即使 left 和 right 都很大，对于 Java 语言来说，(left + right) 可能发生整型溢出，但是无符号右移一位仍然能够得到正确的结果，而 Python 整型溢出了以后，类型自动升为 long 类型。

所以，在理解的基础上记住这个结论：取中位数用“+” 和“无符号右移”更优，事实上，Java 的 JDK 就是这么做的。